package 排序;

import java.util.Arrays;

public class 直接插入排序 {
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 9, 1, 2, 7, 6};
        // 获取数组长度
        int n = arr.length;
        // 外循环，从第二个元素开始遍历，因为第一个元素本身就是有序的
        for (int i = 1; i < n; i++) {
            // 将当前元素保存到变量中
            int current = arr[i];
            // 将需要比较的元素的索引值设置为 i-1，即当前元素的前一个元素
            int j = i - 1;
            // 内循环，将当前元素与前面有序部分中的元素依次比较，直到找到合适的位置插入当前元素
            while (j >= 0 && arr[j] > current) {
                // 如果前一个元素大于当前元素，将前一个元素移动到当前元素上
                arr[j + 1] = arr[j];
                // 继续向前查找
                j--;
            }
            // 将当前元素插入到合适的位置
            arr[j + 1] = current;
        }
        System.out.println(Arrays.toString(arr));
    }

}
